0922. 按奇偶排序数组 II【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双指针

1. 📝 题目描述

• leetcode

给定一个非负整数数组 nums， nums 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是奇数；当 nums[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

---

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

---

示例 2：

输入：nums = [2,3]
输出：[2,3]

---

提示：

• 2 <= nums.length <= 2 * 10^4
• nums.length 是偶数
• nums 中一半是偶数
• 0 <= nums[i] <= 1000

---

进阶：可以不使用额外空间解决问题吗？

2. 🎯 s.1 - 双指针

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParityII = function (nums) {
  let i = 0 // 偶索引
  let j = 1 // 奇索引
  const n = nums.length

  while (i < n && j < n) {
    const evenIdxOk = (nums[i] & 1) === 0
    const oddIdxOk = (nums[j] & 1) === 1

    if (!evenIdxOk && !oddIdxOk) {
      // 偶位是奇数、奇位是偶数，交换纠正
      const t = nums[i]
      nums[i] = nums[j]
      nums[j] = t
      i += 2
      j += 2
    } else {
      if (evenIdxOk) i += 2
      if (oddIdxOk) j += 2
    }
  }
  return nums
}

• 时间复杂度：$O(n)$，双指针线性遍历并按需交换
• 空间复杂度：$O(1)$，原地调整

算法思路：

• 维护两个指针：i 指向偶索引，j 指向奇索引，步长均为 2
• 若 nums[i] 为偶则 i+=2；若 nums[j] 为奇则 j+=2
• 当出现偶位是奇数、奇位是偶数时交换两者并同时前进
• 直到任一指针越界，数组即可满足“值的奇偶与索引奇偶匹配”